/**
 * 
 */
package uk.ac.manchester.cs.graph.alg;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import uk.ac.manchester.cs.graph.Graph;

/**
 * Breadth-first search
 * 
 * @author Pavel Klinov
 *
 * pklinov@cs.man.ac.uk, pklinov@clarkparsia.com
 * 
 * Mar 6, 2011
 */
public class BFS implements GraphSearchAlgorithm {

	
	public <V,E> void search(Graph<V,E> graph, V start, VertexVisitor<V> visitor) {
		
		List<V> frontier = new ArrayList<V>();
		Set<V> visited = new HashSet<V>(graph.getVertices().size());
		
		frontier.add( start );
		
		while (!frontier.isEmpty()) {
		
			V current = frontier.remove( 0 );

			visited.add( current );
			
			if (visitor.visit( current )) {
				//Get unvisited neighbors
				Set<V> neighbors = graph.getAdjacentVertices( current );
				
				neighbors.removeAll( visited );
				frontier.addAll( neighbors );	
			}
		}
	}
}
